package HuaWeiOd.AA;

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

/**
 * 在第一人称射击游戏中，玩家通过键盘的 A、S、D、W 四个按键控制游戏人物分别向左、向后、向右、向前进行移动，从而完成走位。
 * 假设玩家每按动一次键盘，游戏人物会向某个方向移动一步，如果玩家在操作一定次数的键盘并且各个方向的步数相同时，此时游戏人物必定会回到原点，则称此次走位为完美走位。
 * 现给定玩家的走位（例如：ASDA）,请通过更换其中一段连续走位的方式使得原走位能够变成一个完美走位。
 * 其中待更换的连续走位可以是相同长度的任何走位。
 * 请返回待更换的连续走位的最小可能长度。
 * 若果原走位本身是一个完美走位，则返回 0。
 *
 * 输入
 *
 * 输入为由键盘字母表示的走位s，例如：ASDA
 *1. 走位长度 1≤ $s.length$ ≤$10^5$
 *
 * 2. `s.length` 是 `4` 的倍数
 *
 * 3. `s` 中只含有 `A`, `S`, `D`, `W` 四种字符
 *
 * ## 示例一
 *
 *
 *
 * ### 输入
 *
 *
 *
 * ```plaintext
 *
 * ASDW
 *
 * ```
 *
 *
 *
 * ### 输出
 *
 *
 *
 * ```plaintext
 *
 * 0
 *
 * ```
 *
 *
 *
 * ### 说明
 *
 *
 *
 * 已经是完美走位了。
 *
 *
 *
 * ## 示例二
 *
 *
 *
 * ### 输入
 *
 *
 *
 * ```plaintext
 *
 * AASW
 *
 * ```
 *
 *
 *
 * ### 输出
 *
 *
 *
 * ```plaintext
 *
 * 1
 *
 * ```
 *
 *
 *
 * ### 说明
 *
 *
 *
 * 需要把一个 `A` 更换成 `D`，这样可以得到 `ADSW` 或者 `DASW`。
 *
 *
 *
 * ## 示例三
 *
 *
 *
 * ### 输入
 *
 *
 *
 * ```plaintext
 *
 * AAAA
 *
 * ```
 *
 *
 *
 * ### 输出
 *
 *
 *
 * ```plaintext
 *
 * 3
 *
 * ```
 *
 *
 *
 * ### 说明
 *
 *
 *
 * 可以替换后 `3` 个 `A`，得到 `ASDW`。 作者：发量迷人的乔喻 https://www.bilibili.com/read/cv22247529?from=search 出处：bilibili
 * @author caihe
 * @date 2023/4/11 22:22
 */
public class 完美走位 {
    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
//
//        String str = sc.nextLine();
//        char[] chars = str.toCharArray();
//        
//        int[] pos = {0 ,0};
//        
//        for (char c : chars) {
//            
//            switch (c) {
//                case 'A':
//                    pos[0]--;
//                    break; 
//                case 'D':
//                    pos[0] ++;
//                    break;
//                case 'W':
//                    pos[1]++;
//                    break;
//                case 'S':
//                    pos[1]--;
//                    break;
//            }
//        }
//        if (pos[0] == 0 && pos[1] == 0) {
//            System.out.println(0);
//        } else if (pos[0] == 0) { 
//            System.out.println(Math.abs(pos[1]));
//        } else if (pos[1] == 0) {
//            System.out.println(Math.abs(pos[0]));
//        } else {
//            
//            System.out.println(Math.min(Math.abs(pos[0]), Math.abs(pos[1])));
//        }
        System.out.println(q004("AAWS"));
    }

    public static int q004(String input) {
        Map<Character, Integer> charCount = new HashMap<>();
        charCount.put('W', 0);
        charCount.put('A', 0);
        charCount.put('S', 0);
        charCount.put('D', 0);
        for (int i = 0; i < input.length(); i++) {
            charCount.put(input.charAt(i), charCount.get(input.charAt(i)) + 1);
        }

        int num = charCount.get(input.charAt(0));
        boolean needCal = false;
        for (Integer c : charCount.values()) {
            if (!c.equals(num)) {
                needCal = true;
                break;
            }
        }

        if (!needCal) {
            return 0;
        }

        int left = 0;
        int right = 0;
        int target = input.length();
        charCount.put(input.charAt(right), charCount.get(input.charAt(right)) - 1);
        while (left < input.length()) {
            int maxCount = 0;
            for (Integer c : charCount.values()) {
                maxCount = Math.max(maxCount, c);
            }

            int lackCharNum = 0;
            for (Integer c : charCount.values()) {
                lackCharNum += maxCount - c;
            }

            int length = right - left + 1;
            int completeNum = length - lackCharNum;
            if (completeNum >= 0 && completeNum % 4 == 0) {
                target = Math.min(target, length);
                charCount.put(input.charAt(left), charCount.get(input.charAt(left)) + 1);
                left++;
            } else {
                right++;
                if (right >= input.length()) {
                    break;
                }
                charCount.put(input.charAt(right), charCount.get(input.charAt(right)) - 1);
            }
        }

        return target;
    }
}
